/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package algorithms;

import data.Array;
import error.OutOfMemoryException;
import error.ProgrammingErrorException;

/**
 * An example of using the Selection sort Algorithm
 * The selection sort iterates through the array finding the biggest value
 * and swaps it with index "stop". stop will start at numElements - 1 and end at
 * 1. Basically, we select the biggest value, put it on the right,
 * then we make the array smaller, find the next biggest value, put it on the
 * left of the bigest value and so on.
 * 
 * O(N^2)
 * 
 * @author jchoy
 */
public class SelectionSort {
    public SelectionSort() {
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            SelectionSort sort = new SelectionSort();
            SelectionSort.SelectionSortedArray array 
                = sort.new SelectionSortedArray();
            
            System.out.println( "Filling Array...");
            array.fillWithRandomNumbers(50000);
            
            System.out.println( "Selection Sorting..." );
            
            long startTime = System.currentTimeMillis();
            array.sort();
            long stopTime = System.currentTimeMillis();
            long sortTime = stopTime - startTime;
            
            System.out.println( "It took " + Long.toString(sortTime) + "ms");
            
            System.out.print( "Testing sort...");
            
            if ( array.isOrdered() == true) {
                System.out.println( "PASS!" );
            } else {
                System.out.println( "FAIL!" );
            }
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
    }
    
    
    class SelectionSortedArray extends Array {
        public SelectionSortedArray() {
        }
        
        /**
         * Sorts the array using selection sort.
         * 
         * @throws ProgrammingErrorException 
         */
        public void sort() throws ProgrammingErrorException {
            int maxValueIndex = -1;
            int start = 0;
            int stop = 0;

            /* Start with the WHOLE array and move the stop point to the
             * left. We use getNumElements() - 1 because the stop point is the
             * place we will be inserting which has to be a valid index
             */
            for ( stop = getNumElements() - 1; stop > 0; stop-- ) {
                
                /* set the maximum value as the last point */
                maxValueIndex = stop;
                
                /* Iterate through this sub array and if we find a new smallest
                 * element, we will swap it with the starting point element
                 */
                start = 0;
                for ( start = 0; start < stop; start++) {
                    if (array[start] > array[maxValueIndex]) {
                        maxValueIndex = start;
                    }
                }
                swapValue( start, maxValueIndex );
            }
        }
    }
    
    

}
